The regular expression is a notation which expresses an arbitrary string as a pattern by combining normal characters and particular characters having special meanings so-called metacharacters.
The string matching (pattern matching) using the regular expression is applied to various kinds of fields. For example, it is used for a string search from a certain document file, a search of a specific string from packet payloads in a network in a network security field and the like.
Recently, network bandwidths have been drastically increased. Therefore, particularly, in a network, when a pattern matching is performed in packet payloads and the like using a regular expression, it should be implemented with high search throughput adapted to a network bandwidth.
Generally, in a microprocessor, a pattern matching using a regular expression is implemented using a NFA (Non-deterministic Finite Automaton) or a DFA (Deterministic Finite Automaton) which is created from a given search target pattern of a regular expression.
A conversion method from a regular expression into a NFA or a DFA is, for example, disclosed in a non-patent literature 1 (Yoshiyuki Kondo, “The Standard Text: Algorithm and Data Structure for C-programmer”, SoftBank Publishing, 1998, pp. 297-330). The non-patent literature 1 discloses that a regular expression is converted into a syntax tree, a NFA is created from the syntax tree, and then, a DFA is created from the NFA.
FIG. 1 shows an example of the syntax tree of “a(bc)*(d|e)f” using the regular expression. FIG. 2 shows an example of the NFA obtained by converting the syntax tree of “a(bc)*(d|e) f” using the regular expression. Here, the NFA of FIG. 2 is an example of the NFA not including a ε transition (epsilon-transition). The ε transition is a particular transition in which a transition can be carried out without having any input.
In the DFA in which there is only one destination of a state transition for input characters in a certain state, a pattern matching can be implemented in a constant speed per character, namely, in a processing time O(1). Therefore, for an input stream (a search target string) with a length of m, the processing time O(m) is required. There is a concern that, for a length n of the regular expression, the number of states of the DFA increases to the O(2n) in the worst case. Therefore, there is a possibility that the memory amount for requiring to hold the states increases explosively. This is also pointed out in a patent literature 1 (JP-P 2005-537550 A), the non-patent literature 1 and a non-patent literature 2 (Reetinder Sidhu, Viktor K. Prasanna, “Fast Regular Expression Matching using FPGAs”, Proceedings of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2001, pp. 227-238).
On the other hand, in the NFA, there is a case that a plurality of destinations of a state transition for input characters in a certain state. In this case, in a microprocessor which executes a serial processing, the NFA implements a pattern matching in a processing time O(n) per character. Here, the n is the length of the regular expression. Therefore, for the input stream with the length of m, the processing time O(mn) is required. However, the number of states increases to the O(n) which is smaller than that of the DFA.
Recently, for example, in the non-patent literature 2, a method for a high speed pattern matching is proposed which makes the NFA be an actual circuit to be embedded to a reconfigurable device such as a FPGA (Field Programmable Gate Array).
FIG. 3 is a circuit diagram of a basic block used for making the NFA be an actual circuit in the non-patent literature 2. This unit circuit includes: a Flip-Flop (F/F) 502, a comparator 602 and an AND gate 803. The Flip-Flop 502 is for configuring each state of the NFA. The comparator 602 is for comparing a character of a transition condition from the state with an input text character. The AND gate 803 is for creating a state transition signal based on the output of the Flip-Flop and the output of the comparator.
According to the non-patent literature 2, by providing with a plurality of the unit blocks having such configurations, arranging the plurality of the unit blocks appropriately and further connecting a combinational circuit such as an AND gate, an OR gate and the like, the target NFA is made to be the actual circuit.
FIG. 4 is a circuit diagram of the pattern matching circuit corresponding to the “a(bc)*(d|e)f” using the regular expression according to the non-patent literature 2. In this method, by taking advantages of parallel processing features using hardware, while the number of states of the NFA maintains the O(n), the processing time per character can be reduced to the O(1) similar to that of the DFA. Therefore, for the input stream with the length m, the pattern matching can be carried out in the processing time of the O(m).
On the other hand, in the above method, when the revision of the pattern of the regular expression embedded to the FPGA is performed by changing, adding, deleting and the like, a reconfiguration processing (hereinafter referred to as compiling of FPGA) such as a correction and/or a synthesis of a HDL (Hardware Description Language) like a verilog-HDL and a VHDL (Very high-speed integrated circuit Hardware Description Language), a PAR (Place and Route) and/or a programming for the FPGA is required. Consequently, even if one pattern is desired to be revised, a processing of a whole system including the FPGA should be stopped during the reconfiguration. In addition, based on the reason mentioned above, there is a problem that it is not suitable to be configured using an ASIC (Application Specific Integrated Circuit) for an actual dedicated circuit.
In order to solve the above mentioned problem, a circuit architecture is proposed in a non-patent literature 3 (Divyasree J, Rajashekar H, Kuruvilla Varghese, “Dynamically Reconfigurable Regular Expression Matching Architecture”, Proceedings of the 19th IEEE International Conference on Application-Specific Systems, Architectures and Processors, 2008, pp. 120-125) and the patent literature 1.
The method shown in the non-patent literature 3, similar to that shown in the non-patent literature 2, by providing with a plurality of unit blocks (called a basic block in the non-patent literature 3), a state of the NFA is made to be the actual circuit. Here, the circuit of the non-patent literature 3 is slightly different from that of the non-patent literature 2 in the connection relation of the output signals and the like from the Flip-Flop and the comparator.
In addition, the non-patent literature 3 proposes an architecture including generic blocks, each of which includes: an 8 bits counter realizing a CR(Constrained Repetition) of the certain number of times such as “R{n}” of the regular expression (n times repetition of R of the regular expression), “R{n,m}” of the regular expression (equal to or more than n and equal to or less than m times repetition of R of the regular expression) and the like; a count decoder judging the number of times of the CR; and a MUX (MUltipleXer) selecting multiple signal lines. The generic blocks are arranged in line like an array shape and are connected to respective input and output signals.
This architecture is supposed to be configured on the FPGA. In addition, the operation of each of the MUX and the count decoder in each generic block is determined by changing a content of an LUT (Look-Up Table) composed of a memory (SRAM: Static Random Access Memory) which determines a circuit configuration of the FPGA.
In the non-patent literature 3, the FPGA produced by the Xilinx Incorporated is supposed. The content of the LUT is supposed to be changed by using a SRL (Shift Register LUT). However, by providing a register and a memory corresponding to the SRL, it is considered to be configured using the ASIC.
In this method, as described above, the operation of the MUX configured in the generic block implemented on the FPGA is changed. This makes it possible to realize a dynamic reconfiguration which configures the regular expression without compiling the FPGA.
In this architecture, the generic blocks are connected in line like an array shape. In addition, there is only one feedback signal from a certain generic block to a previous generic block. Consequently, in this architecture, there is a problem that the regular expressions which can be configured are limited. For example, the regular expression such as “a(bcd)*e” can be configured. However, the regular expression in which a metacharacter exists in a nest such as “a(b+cd)*e” cannot be configured.
In addition, the patent literature 1 discloses a reconfigurable NFA circuit architecture in which a connection configuration and a state transition condition can be reconfigured bated on values set in a register array. This architecture is supposed to be configured using the ASIC. However, as similar to the above-mentioned architecture, it can be configured using the FPGA.
The architecture in the patent literature 1 is provided with: register arrays having functions of the states of the NFA; and wiring lines from each register indicating the state to all registers indicating respective states. In addition, it is provided with register arrays for setting connections between the states. Based on a configuration of switches using values set in the registers, the connections between the registers indicating the states can be set. Further, it is provided with register groups for setting state transition information from respective states to the transition destinations. For example, when a transition is carried out using a character of the regular expression, a character of the transition condition is set at the corresponding positions in the register group. The set value is compared with an input text character. If the set value matches the character, a logical AND is carried out between a signal indicating the matching result and a signal as the corresponding transition condition to establish the state transition. In this method, by rewriting both of the register arrays in which the connection information (switches) between the states is set and the register groups in which the state transition information is set, the NFA which is expressed by the desired regular expression can be dynamically reconfigured.
This architecture can dynamically configure all of the NFA. On the other hand, for the general-purpose, wiring lines of respective states are prepared. Therefore, the number of the wiring lines, the number of the register arrays setting the connection information (switches) between the states and the number of the register groups setting the state transition information are increased at a rate of O(N2). That is, there is a problem in the scalability with respect to the number of states.
In summary, the circuit architecture which can reconfigure the NFA indicating the regular expression and the general-purpose NFA as mentioned above have following problems.
The first problem appears in the reconfigurable NFA circuit in which the blocks (modules) capable of partially configuring the specific regular expression are connected in one-dimensional array shape. In this reconfigurable NFA circuit, for example, the regular expression in which a metacharacter exists in a nest such as “a(b+cd)*e” cannot be configured. That is, the first problem is that there are limiting conditions for configuring the regular expression.
The reason is that the blocks (modules) (generic block in the non-patent literature 3) capable of partially configuring the specific regular expression are connected in one-dimensional array shape, and therefore the limiting conditions for configuring the regular expression arises. This is because there is only one feedback signal from the certain block to the previous block. In addition, this is because the number of signals which is made to pass through the later stage blocks is limited, when there are multiple signals to be directly connected to a several blocks away.
The second problem appears in the architecture, which is provided with the wiring lines from each register indicating the state to all registers and can dynamically reconfigure the NFA by reconfiguring the connection configuration between the states and the state transition condition using the set values in the register array. This architecture can configure all of the NFA having whatever transition. On the other hand, the amount of hardware is increased at a rate of O(N2) with respect to the number of states: N. Thus, the second problem is that there is a problem in the scalability with respect to the number of states.
The reason is that the architecture is the circuit which can configure the general-purpose NFA. That is, all wiring lines of respective states, the register arrays setting the connection information (switches) between the states, and the register groups setting the state transition information is required to be prepared.
As another technique, a non-patent literature 4 (Reetinder Sidhu, “Efficient Computation Using Self-Reconfiguration”, University of Southern California, Doctoral dissertation (PhD Thesis), 2005, pp. 159-162) discloses “The layout of an arbitrary binary tree t of size (the number of nodes) n (n>0) can be performed in n×(layers(t)+1) cells” and “If t is a binary tree of size (the number of nodes) 2n−1 (n>1), then layers(t) is at most n−1”. These lead to “The layout of an arbitrary binary tree t of size (the number of nodes) 2n−1 (n>1) can be performed in at most (2n−1)×n cells.”